package sort;

import java.text.BreakIterator;
import java.util.Arrays;

/**
 * @Classname QuickSort
 * @Author happytaohaha
 * @Date 2020/2/29
 * @Description 快速排序
 * 一个标志位，然后交替进行左右移动
 */
public class QuickSort {

    public static int[] quickSort(int[] array) {
        int len = array.length;
        quickSort(array, 0, len - 1);
        return array;
    }

    /**
     * 子方法  先进行找到基准点的位置 将基准点位置固定，然后对子序列进行排序
     *
     * @param array
     * @param start
     * @param end
     */
    public static void quickSort(int[] array, int start, int end) {
        if(start >=end){
            return;
        }
        //找基准点位置，并排好他的位置
        int location = sortAndLocation(array, start, end);
        quickSort(array, start, location - 1);
        quickSort(array, location + 1, end);
    }

    /**
     * 找基准点位置，并排好他的位置
     *
     * @param array
     * @param start
     * @param end
     * @return 返回基准点
     */
    private static int sortAndLocation(int[] array, int start, int end) {
        int point = array[start];
        int left = start+1;
        int right = end;
        int temp;
        while (true) {
            //从左往右扫描碰到第一个比基准点大的值
            while (array[left] < point && left < right) {
                left++;
            }
            //从右往左扫
            while (array[right] >= point && left < right) {
                right--;
            }
            //左右指针相遇 ,指向了该交换的下一个位置
            if (left == right) {
                break;
            }
            //左右交换
            temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }
        temp = point;
        array[start] = array[right-1];
        array[right-1] = temp;
        return right-1;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(quickSort(new int[]{7,8,4,6,5,1,2,3})));
    }
}
